/*
	解法：双指针
	为什么：只要遇到“原地修改”+“删除”/“保留”元素这类题型，第一反应就是双指针！
	时间复杂度：O(n)，空间复杂度：O(1)
 */

#include <iostream>
#include <vector>

using namespace std;


class Solution 
{
public:
	int removeElement(vector<int>& nums, int val) 
	{
		// 定义左指针，表示下一个要写入的位置
		int left = 0;
		
		// 右指针逐个遍历整个数组
		int right = 0;
		while (right < (int)nums.size()) 
		{
			// 如果右指针指向的元素不等于 val
			if (nums[right] != val) 
			{
				// 就把该元素写到左指针的位置
				nums[left] = nums[right];
				
				// 然后左指针向右移动一位，表示下一个写入位置
				left++;
			}
			// 无论右指针等于或不等于val, 右指针都像右移一位
			right++;
		}
		
		// 返回新的长度（即不等于 val 的元素个数）
		//left由于最后+1恰好就是nums中与val不同的元素的数量
		return left;
	}
};

int main() 
{
	Solution sol;
	vector<int> nums = {0, 1, 2, 3, 4, 5, 2, 7, 2};
	int val;
	
	cout << "请输入要移除的值 val: ";
	cin >> val;
	
	int k = sol.removeElement(nums, val);
	
	cout << "移除后的有效长度 k = " << k << endl;
	cout << "前 k 个元素为: ";
	for (int i = 0; i < k; i++) 
	{
		cout << nums[i] << " ";
	}
	cout << endl;
	
	return 0;
}


